package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/6.
 */
public class Generate_Parentheses {
    private List<String> rst = new LinkedList<String>();
    private StringBuffer sb = new StringBuffer("");
    private void generate(int L,int R,int size){
        if(L==0){
            for(;R>0;R--){
                sb.append(")");
                size--;
            }
            if(size==0){
                rst.add(sb.toString());
            }
        }
        else{
            int sbSize = sb.length();
            sb.append("(");
            generate(L-1,R,size+1);
            sb.delete(sbSize,sb.length());
            if (R>0 && size>0){
                sb.append(")");
                generate(L,R-1,size-1);
            }
        }
    }
    public List<String> generateParenthesis(int n) {
        if(n<=0)
            return rst;
        int L = n,R = n,size = 0;
        generate(L,R,size);
        return rst;
    }

    public static void main(String[] args){
        Generate_Parentheses generate_parentheses = new Generate_Parentheses();
        System.out.println(generate_parentheses.generateParenthesis(8));
    }
}
